package tep;

public class Trie {

    static class TrieNode{
        boolean isEnd;
        TrieNode[] ch;
        public TrieNode(){
            ch = new TrieNode[26];
        }
    }

    private TrieNode root;


    public Trie(){
        root = new TrieNode();
    }

    public void insert(String str){
        TrieNode node = root;
        for(int i=0;i<str.length();i++){
            char c = Character.toLowerCase(str.charAt(i));
            if(node.ch[c-'a']==null){
                node.ch[c-'a'] = new TrieNode();
            }
            node = node.ch[c-'a'];
        }
        node.isEnd = true;
    }

    public boolean startwith(String str){
        TrieNode node = root;
        for(char ch:str.toCharArray()){
            if(node.ch[Character.toLowerCase(ch)-'a']==null){
                return false;
            }
            node = node.ch[Character.toLowerCase(ch)-'a'];
        }
        return true;
    }

    public boolean match(String str){
        TrieNode node = root;
        for(char ch:str.toCharArray()){
            if(node.ch[Character.toLowerCase(ch)-'a']==null){
                return false;
            }
            node = node.ch[Character.toLowerCase(ch)-'a'];
        }
        return node.isEnd;
    }
    static  boolean falg  = false;
    public boolean cal(String str){
        falg = false;
        dfs(root,str,0,0);


        return falg;



    }

    public void dfs(TrieNode node,String str,int index,int use){
        if(node.isEnd&&use==1&&index==str.length()){
            falg = true;
            return;
        }
        for(int i=0;i<26;i++){
            if(use==0){
                if(node.ch[i]!=null){
                    int num = Character.toLowerCase(str.charAt(index))-'a';
                    if(num==i){
                        dfs(node.ch[i],str,index+1,0);
                    }else {
                        dfs(node.ch[i],str,index+1,1);
                    }
                }
            }else {
                if(node.ch[i]!=null){
                    int num = Character.toLowerCase(str.charAt(index))-'a';
                    if(num==i){
                        dfs(node.ch[i],str,index+1,1);
                    }
                }
            }
        }



    }





    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("Hello");
        trie.insert("HelloWorld");
        System.out.println(trie.startwith("hello"));
        System.out.println(trie.match("hellowORLd"));

        System.out.println("----------------------");

        System.out.println(trie.cal("helkowORLd"));

    }







}
